package com.example.demo.algorithm.graph;

/**
 * @Author: xiatian
 * @CreateTime: 2022/2/5 12:22 下午
 * @Description:深度优先搜索
 */
public class DepthFirstSearch {
    //索引代表顶点，值标识当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;

    /**
     * 构造深度优先搜索对象，使用深度优先搜索对象，找出g图中顶点s的所有相通的顶点
     *
     * @param g
     * @param s
     */
    public DepthFirstSearch(Graph g, int s) {
        this.marked = new boolean[g.V()];
        this.count = 0;
        dfs(g, s);
    }

    /**
     * 使用深度优先搜索对象，找出g图中顶点v的所有相通的顶点
     *
     * @param g
     * @param v
     */
    private void dfs(Graph g, int v) {
        //把v标识为已搜索
        marked[v] = true;
        for (Integer w : g.adj(v)) {
            //判断当前w顶点有没有被搜索过，没有被搜索过，则递归调用dfs方法进行深度搜索
            if (!marked[w]) {
                dfs(g, w);
            }
        }
        //相通顶点数量+1
        count++;

    }

    /**
     * 判断w顶点与s顶点是否相通
     *
     * @param w
     * @return
     */
    public boolean marked(int w) {

        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }


}
